//给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并
//返回这颗 二叉树 。 
//
// 
//
// 示例 1: 
// 
// 
//输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
//输出：[3,9,20,null,null,15,7]
// 
//
// 示例 2: 
//
// 
//输入：inorder = [-1], postorder = [-1]
//输出：[-1]
// 
//
// 
//
// 提示: 
//
// 
// 1 <= inorder.length <= 3000 
// postorder.length == inorder.length 
// -3000 <= inorder[i], postorder[i] <= 3000 
// inorder 和 postorder 都由 不同 的值组成 
// postorder 中每一个值都在 inorder 中 
// inorder 保证是树的中序遍历 
// postorder 保证是树的后序遍历 
// 
//
// Related Topics 树 数组 哈希表 分治 二叉树 👍 1073 👎 0


package LeetCode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ldltd
 * @date 2023-08-18 00:53:37
 * @description 106.从中序与后序遍历序列构造二叉树
 */
public class ConstructBinaryTreeFromInorderAndPostorderTraversal{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new ConstructBinaryTreeFromInorderAndPostorderTraversal().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
public class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode() {}
	TreeNode(int val) { this.val = val; }
	TreeNode(int val, TreeNode left, TreeNode right) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

class Solution {
		 /*
首先在后序遍历序列中找到根节点(最后一个元素)
根据根节点在中序遍历序列中找到根节点的位置
根据根节点的位置将中序遍历序列分为左子树和右子树
根据根节点的位置确定左子树和右子树在中序数组和后续数组中的左右边界位置
递归构造左子树和右子树
返回根节点结束
需要定义几个变量帮助我们进行树的还原

HashMap memo 需要一个哈希表来保存中序遍历序列中,
元素和索引的位置关系.因为从后序序列中拿到根节点后，
要在中序序列中查找对应的位置,从而将数组分为左子树和右子树
int ri 根节点在中序遍历数组中的索引位置
中序遍历数组的两个位置标记 [is, ie]，is 是起始位置，ie 是结束位置
后序遍历数组的两个位置标记 [ps, pe] ps 是起始位置，pe 是结束位置

在找到根节点位置以后，我们要确定下一轮中，左子树和右子树在中序数组和后续数组中的左右边界的位置。

左子树-中序数组 is = is, ie = ri - 1
左子树-后序数组 ps = ps, pe = ps + ri - is - 1 (pe计算过程解释，后续数组的起始位置加上左子树长度-1 就是后后序数组结束位置了，左子树的长度 = 根节点索引-左子树)
右子树-中序数组 is = ri + 1, ie = ie
右子树-后序数组 ps = ps + ri - is, pe - 1


*/
    public TreeNode buildTree(int[] inorder, int[] postorder) {
		for (int i = 0; i < inorder.length; i++) {
			memo.put(inorder[i],i);
		}
		TreeNode root=buildTree(0,inorder.length-1,0,postorder.length-1,postorder);
		return root;
    }
	Map<Integer,Integer> memo=new HashMap<>();
	public TreeNode buildTree(int il,int ir,int pl,int pr,int[] post){
		if(ir<il||pr<pl)return null;
		int root=post[pr];
		int rootIndex=memo.get(root);
		TreeNode node =new TreeNode(root);
		node.left=buildTree(il,rootIndex-1,pl,pl+rootIndex-il-1,post);
		node.right=buildTree(rootIndex+1,ir,pl+rootIndex-il,pr-1,post);
		return node;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
